import numpy as np
from . import LocalSearchOperator, register_operator


class BackwardInsertionOperator(LocalSearchOperator):
    """后向插入(Backward Insertion)局部搜索算子"""

    def __init__(self):
        self.name = "backward_insertion"
        self.supported_problems = ["tsp"]

    def efficient_backward_insertion(self, solution, problem_instance, intensity=15):
        """高效的后向插入实现"""
        n = len(solution)
        current_solution = solution.copy()
        current_cost = problem_instance.evaluate(current_solution)
        improved = True
        iterations = 0

        while improved and iterations < intensity:
            improved = False

            # 尝试多个随机插入操作
            for _ in range(min(100, n * n)):  # 限制尝试次数
                # 随机选择一个城市和一个插入位置
                i = np.random.randint(0, n - 1)  # 要移动的城市位置（不能是最后一个）
                j = np.random.randint(i + 2, n)  # 插入位置（在i之后）

                if j == i or j == i + 1:  # 跳过无效位置
                    continue

                # 执行插入操作
                city_to_move = current_solution[i]
                new_solution = np.concatenate([
                    current_solution[:i],
                    current_solution[i + 1:]
                ])
                new_solution = np.concatenate([
                    new_solution[:j],
                    [city_to_move],
                    new_solution[j:]
                ])

                # 评估新解
                new_cost = problem_instance.evaluate(new_solution)

                # 如果成本降低，则接受插入
                if new_cost < current_cost:
                    current_solution = new_solution
                    current_cost = new_cost
                    improved = True
                    break  # 找到一个改进就跳出内层循环

            iterations += 1

        improvement = problem_instance.evaluate(solution) - current_cost
        return current_solution, improvement

    def __call__(self, solution, problem_instance, intensity=15):
        """应用后向插入局部搜索"""
        if not self.is_applicable(problem_instance):
            return solution, 0

        n = len(solution)
        if n < 4:  # 后向插入需要至少4个城市
            return solution, 0

        # 使用高效实现
        return self.efficient_backward_insertion(solution, problem_instance, intensity)


# 注册算子
register_operator("backward_insertion", BackwardInsertionOperator())